Bellman-Ford Algorithm

contents

벨만-포드 알고리즘은 가중치가 있는 방향 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 그래프 탐색 알고리즘입니다.

다익스트라와 같은 다른 알고리즘에 비해 갖는 주된 이점은 음수 가중치 간선을 처리할 수 있다는 것입니다. 또한, 무한히 순환하여 "더 짧은" 경로(음의 무한대)를 만들 수 있는 음수 가중치 사이클을 탐지할 수도 있습니다.

💡 핵심 아이디어: 반복적인 완화

벨만-포드는 동적 프로그래밍 알고리즘입니다. 그래프의 모든 간선을 반복적으로 "완화(relax)"하는 방식으로 작동합니다. 핵심 아이디어는 다음과 같습니다.

시작점 S에서 다른 정점 v까지의 최단 경로는 최대 V-1개의 간선(여기서 V는 정점의 수)을 가질 수 있습니다. 만약 경로가 이보다 더 많은 간선을 가진다면, 이는 반드시 사이클을 포함하고 있어야 합니다.

이를 바탕으로, 알고리즘은 라운드별로 최단 경로를 찾습니다.

• 1 라운드: 최대 1개의 간선으로 이루어진 모든 최단 경로를 찾습니다.
• 2 라운드: 최대 2개의 간선으로 이루어진 모든 최단 경로를 찾습니다.
• ...
• V-1 라운드: 최대 V-1개의 간선으로 이루어진 모든 최단 경로를 찾습니다.

이 과정을 완화(relaxation) 라고 부릅니다. 가중치 w를 가진 모든 간선 (u, v)에 대해, 알고리즘은 현재까지 알려진 v까지의 최단 경로가 u를 먼저 거쳐가는 경로로 개선될 수 있는지 확인합니다.

이 확인 작업은 다음과 같습니다. if (distance[u] + weight(u, v) < distance[v])

🚶 알고리즘 단계별 상세 설명

V개의 정점과 E개의 간선을 가진 그래프와 시작 정점 S가 있다고 가정합니다.

1단계: 초기화

1. V 크기의 distances 배열을 생성합니다.
2. 시작 정점 S까지의 거리를 0으로 초기화합니다.
3. 다른 모든 정점까지의 거리를 무한대(∞)로 초기화합니다.

distances[S] = 0
S를 제외한 모든 정점 v에 대해:
    distances[v] = ∞

2단계: 반복적인 완화

이것이 메인 루프입니다. V-1번 반복해야 합니다.

for i from 1 to V-1:
    그래프의 가중치 w를 가진 각 간선 (u, v)에 대해:
        // v까지 더 짧은 경로가 발견되었는지 확인
        if distances[u] + w < distances[v]:
            distances[v] = distances[u] + w
            // (선택 사항: 경로 저장)
            // predecessor[v] = u

V-1번의 반복이 끝나면, distances 배열은 음수 가중치 사이클이 없다고 가정할 때 모든 정점까지의 최단 경로를 포함하게 됩니다.

3단계: 음수 사이클 확인

이것이 벨만-포드를 강력하게 만드는 마지막 핵심 단계입니다. 완화 루프를 한 번 더(V번째) 실행합니다.

그래프의 가중치 w를 가진 각 간선 (u, v)에 대해:
    if distances[u] + w < distances[v]:
        // 여전히 더 짧은 경로가 발견됨!
        // 이는 음수 사이클이 존재할 때만 가능함.
        Error: "음수 가중치 사이클이 감지되었습니다."

만약 이 루프가 어떤 간선이라도 다시 완화하는 데 성공한다면, 이는 V개의 간선 이후에도 더 짧은 경로가 발견되었음을 의미합니다. 이는 경로가 음수 사이클을 통과할 때만 가능합니다. 이 경우 최단 경로는 정의되지 않으며(음의 무한대), 알고리즘은 사이클이 존재함을 보고합니다.

✍️ 상세 예제

간단한 그래프로 알고리즘을 추적해 보겠습니다.

• 정점: A, B, C, D
• 시작점: A
• 간선:
  • A → B (가중치 6)
  • A → C (가중치 5)
  • C → B (가중치 -2)
  • B → D (가중치 1)
  • C → D (가중치 4)

여기서 V = 4이고 E = 5입니다. V-1 = 3번 반복해야 합니다.

초기화:

distances = { A: 0, B: ∞, C: ∞, D: ∞ }

반복 1 (간선 1개 길이의 경로 찾기):

모든 간선을 확인합니다.

• A → B: distances[A] + 6 < distances[B]? (0 + 6 < ∞) → True. distances[B] = 6 설정.
• A → C: distances[A] + 5 < distances[C]? (0 + 5 < ∞) → True. distances[C] = 5 설정.
• C → B: distances[C] + (-2) < distances[B]? (∞ + (-2) < 6) → False.
• B → D: distances[B] + 1 < distances[D]? (6 + 1 < ∞) → True. distances[D] = 7 설정.
• C → D: distances[C] + 4 < distances[D]? (5 + 4 < 7) → False. 반복 1 종료: distances = { A: 0, B: 6, C: 5, D: 7 }

반복 2 (최대 2개 간선 길이의 경로 찾기):

새로운 거리로 모든 간선을 다시 확인합니다.

• A → B: 0 + 6 < 6 → False.
• A → C: 0 + 5 < 5 → False.
• C → B: distances[C] + (-2) < distances[B]? (5 + (-2) < 6) → 3 < 6 → True. distances[B] = 3 설정.
• B → D: distances[B] + 1 < distances[D]? (3 + 1 < 7) → 4 < 7 → True. distances[D] = 4 설정.
• C → D: distances[C] + 4 < distances[D]? (5 + 4 < 4) → False. 반복 2 종료: distances = { A: 0, B: 3, C: 5, D: 4 } (참고: D까지의 최단 경로(A→C→B→D)는 간선 3개 길이이므로, 확인을 위해 한 번의 반복이 더 필요합니다.)

반복 3 (최대 3개 간선 길이의 경로 찾기):

마지막으로 모든 간선을 한 번 더 확인합니다.

• A → B: 0 + 6 < 3 → False.
• A → C: 0 + 5 < 5 → False.
• C → B: 5 + (-2) < 3 → False.
• B → D: 3 + 1 < 4 → False.
• C → D: 5 + 4 < 4 → False. 반복 3 종료: distances = { A: 0, B: 3, C: 5, D: 4 } 알고리즘이 안정화되었습니다.

사이클 확인 (반복 4):

한 번 더 실행합니다. 어떤 간선도 완화될 수 없습니다. 음수 사이클이 없음으로 결론 내립니다.

최종 최단 경로:

• A에서 A까지: 0
• A에서 B까지: 3 (경로: A→C→B)
• A에서 C까지: 5 (경로: A→C)
• A에서 D까지: 4 (경로: A→C→B→D)

복잡도

• 시간 복잡도: O(V * E)
  • 메인 루프(2단계)는 V-1번 반복합니다.
  • 그 루프 안에서 모든 간선 E를 방문합니다.
  • 사이클 확인(3단계)은 E번 반복합니다.
  • 총: (V-1) * E + E는 O(V * E)로 단순화됩니다.
• 공간 복잡도: O(V)
  • 각 정점의 거리를 저장해야 합니다.

벨만-포드 vs. 다익스트라

벨만-포드는 언제 사용하는가?

1. 음수 가중치 간선이 있을 때: 다익스트라 대신 이 알고리즘을 선택하는 주된 이유입니다.
2. 음수 사이클을 감지해야 할 때: 이것이 독특한 기능입니다. 금융에서 통화를 순환 변환하여 시작보다 더 많은 돈을 갖게 되는 "차익 거래 기회"를 감지하는 데 사용됩니다.
3. 라우팅 프로토콜: 초기의 라우팅 정보 프로토콜(RIP)은 벨만-포드의 변형을 사용하여 네트워크에서 최적의 경로를 찾는 거리-벡터 프로토콜이었습니다.

references